//
//  OrderListAchieved.c
//  SequenceList
//
//  Created by Xavier on 2023/9/25.
//

#include "OrderListAchieved.h"

//功能的实现：
/**
 1、创建顺序表
 2、顺序表的按位的查找、插入、删除
 3、顺序表的合并（除去重复元素）
 4、顺序表的合并（不用去重）
 */


// 顺序表初始化
void SeqListInit(SeqList* psl) {
    psl->size = 0;
    psl->array = (SLDataType*)malloc(sizeof(SLDataType)*10);
    psl->capicity = 10;
    
    if (psl->array == NULL) {
        printf("malloc error\n");
    }
}

// 顺序表销毁
void SeqListDestory(SeqList* psl) {
    for(int i = 0; i < psl->size; i++) {
        psl->array[psl->size] = 0;
        psl->array = NULL;
    }
    psl->capicity = 0;
    psl->size = 0;
    free(psl->array);
}

// 顺序表打印
void SeqListPrint(SeqList* psl) {
    for (int i = 0; i < psl->size; i++) {
        printf("%d ", psl->array[i]);
    }
    printf("\n");
    
}

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl) {
    if (psl->size == psl->capicity) {
        int newCapacity = psl->capicity*1.5;
        psl->array = (SLDataType*)realloc(psl->array, newCapacity*sizeof(SLDataType));
        psl->capicity = newCapacity;
    }
    if (psl->array == NULL) {
        printf("realloc error\n");
    }
}

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x) {
    CheckCapacity(psl);
    psl->array[psl->size] = x;
    ++psl->size;
}

// 顺序表尾删
void SeqListPopBack(SeqList* psl) {
    --psl->size;
}

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x) {
    CheckCapacity(psl);
    if (psl->array == NULL) {
        psl->array[psl->size] = x;
        ++psl->size;
    }
    for (int i = psl->size-1; i >= 0; i--) {
        psl->array[i+1] = psl->array[i];
    }
    ++psl->size;
    psl->array[0] = x;
    
}

// 顺序表头删
void SeqListPopFront(SeqList* psl) {
    assert(psl);
    for (int i = 0; i < psl->size; i++) {
        psl->array[i] = psl->array[i+1];
    }
    --psl->size;
}

// 顺序表查找 - 按值查找
int SeqListFind(SeqList* psl, SLDataType x);

/// 顺序表查找 - 按位查找
int SeqListFind(SeqList* psl, int pos) {
    return psl->array[pos-1];
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, int pos, SLDataType x) {
    CheckCapacity(psl);
    for (int i = psl->size-1; i >= pos-1; i--) {
        psl->array[i+1] = psl->array[i];
    }
    psl->array[pos-1] = x;
    ++psl->size;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, int pos) {
    for (int i = pos-1; i < psl->size; i++) {
        psl->array[i] = psl->array[i+1];
    }
    --psl->size;
}

//合并两个数组 - 不用去除
void SeqListConbine(SeqList* psl1, SeqList* psl2) {
    int newCapacity = psl2->capicity+psl1->capicity;
    int newSize = psl1->size+psl2->size;
    psl1->array = (SLDataType*)realloc(psl1->array, sizeof(SLDataType)*newCapacity);
    psl1->capicity = newCapacity;
    
    int oldSize = psl1->size;
    psl1->size = newSize;
    int j = 0;
    for (int i = oldSize; i < psl1->size; i++) {
        psl1->array[i] = psl2->array[j];
        j++;
        if (j == psl2->size) break;
    }
}


//合并两个数组 - 除去重复数字
//Question1:只需要往psl1中插入psl2时除去重复的数字
//思路：
//1、先排序
//2、要想把2中插入1中，遍历2中的元素去和1每个对比
//3、如果1中没有2的元素则插入
void SeqListConbineRemoveDuplicate(SeqList* psl1, SeqList* psl2) {
    Bubble(psl1);
    Bubble(psl2);
    CheckCapacity(psl1);
    for (int i = 0; i < psl2->size; i++) {
        for (int j = 0; j < psl1->size; j++) {
            if (psl2->array[i] == psl1->array[j]) {
                break;
            }
            if (j == psl1->size-1) {
                psl1->array[psl1->size] = psl2->array[i];
                ++psl1->size;
            }
        }
    }
}


//排序
void Bubble(SeqList* psl) {
    for (int i = 0; i < psl->size; i++) {
        for (int j = 0; j < psl->size - i - 1; j++) {
            if (psl->array[j] > psl->array[j+1]) {
                int tmp  = psl->array[j];
                psl->array[j] = psl->array[j+1];
                psl->array[j+1] = tmp;
            }
        }
    }
}
